package com.lyj.sc.dynamicProgramming.test20220716;

/**
 * @Author: liyangjing
 * @Date: 2022/07/16/10:14
 * @Description: 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
 * 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
 * 本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
 *
 */
public class lastStoneWeightII1 {
    public int lastStoneWeightII(int[] stones) {
        int sum1 = 0;
        for(int s:stones){
            sum1+=s;
        }
        int sum=sum1/2;
        //1.定义dp数组 值的一半定义为背包 而石头定义为重量和价值
        int[] dp = new int[sum+1];
        //2.初始化 已经全部初始化为0
        //3.遍历 先遍历物品 在遍历背包
        for(int i =0;i<stones.length;i++){
            for(int j=sum;j>=stones[i];j--){
                dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum1-dp[sum]*2;
    }
}
